package com.leetcode.tree.bst;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/7/18 19:16
 */
public class LowestCommonAncestor_236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 当为空或者与Q P任意一个相等的时候，返回root
        if (root == null || root == q || root == p) return root;
        // 获取根节点的左右子树，查找是否能够找到p和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) return root;
        // 找不为null的节点
        return left != null ? left : right;
    }

}
